package 数组和链表;

import 抽象数据类型.ListNode;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-13
 */
public class 反转链表 {
    //1.反转链表，递归
    static ListNode reverse(ListNode head) {
        if (head.getNext() == null) {
            return head;
        }
        ListNode last = reverse(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return last;
    }

    //2.反转链表，迭代
    static ListNode reverseIter(ListNode head) {
        ListNode pre = null, nxt, cur = head;
        while (cur != null) {
            nxt = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    //反转a与b之间的链表
    static ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null, cur = a, nxt;
        while (cur != b) {
            nxt = cur.getNext();
            cur.setNext(pre);
            pre = cur;
            cur = nxt;
        }
        return pre;
    }

    //3.按K组反转链表
    static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            if (b == null) {
                return head;
            }
            b = b.getNext();
        }
        ListNode newHead = reverse(a, b);
        a.setNext(reverseKGroup(b, k));
        return newHead;
    }

    //后继
    static ListNode successor = null;

    //4.反转前N个链表
    static ListNode reverseNR(ListNode head, int n) {
        if (n == 1) {
            successor = head.getNext();
            return head;
        }
        ListNode last = reverseN(head.getNext(), n - 1);
        head.getNext().setNext(head);
        head.setNext(successor);
        return last;
    }

    //4.反转前N个链表,非递归
    public static ListNode reverseN(ListNode head, int k) {

        ListNode curNode = head, preNode = null, nextNode = null;
        int index = 0;
        while (index != k && curNode != null) {
            index++;
            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        ListNode temp = preNode;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = nextNode;

        return preNode;

    }

    //5:反转m到n的链表
    static ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        }
        head.setNext(reverseBetween(head.getNext(), m - 1, n - 1));
        return head;
    }
}